////二叉树用二叉链表存放，不用递归也不用栈，返回二叉树T后序序列第一个结点的指针
#include <iostream>

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

TreeNode* findFirstPostorderNode(TreeNode* root) {
    TreeNode* current = root;
    TreeNode* first = nullptr;
    while (current) {
        if (current->left) {
            TreeNode* predecessor = current->left;
            while (predecessor->right && predecessor->right!= current) {
                predecessor = predecessor->right;
            }
            if (!predecessor->right) {
                predecessor->right = current;
                current = current->left;
            } else {
                predecessor->right = nullptr;
                TreeNode* temp = current;
                current = current->right;
                if (!first) {
                    first = temp;
                }
            }
        } else {
            TreeNode* temp = current;
            current = current->right;
            if (!first) {
                first = temp;
            }
        }
    }
    return first;
}


int main() {
    TreeNode* root = new TreeNode(1);
    root->left = new TreeNode(2);
    root->right = new TreeNode(3);
    root->left->left = new TreeNode(4);
    root->left->right = new TreeNode(5);

    TreeNode* firstNode = findFirstPostorderNode(root);
    if (firstNode) {
        std::cout << "First postorder node value: " << firstNode->val << std::endl;
    } else {
        std::cout << "Tree is empty." << std::endl;
    }

    // 释放内存
    //...

    return 0;
}